#define _CRT_SECURE_NO_WARNINGS 1

#include <map>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//class Solution {
//public:
//    struct Greater
//    {
//        bool operator()(const pair<string, int>& m1, const pair<string, int>& m2)
//        {
//            return m1.second > m2.second;
//        }
//    };
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int> m;
//        for (auto wd : words)
//        {
//            m[wd]++;
//        }
//        vector<pair<string, int>> sortVector(m.begin(), m.end());
//        stable_sort(sortVector.begin(), sortVector.end(), Greater());
//        vector<string> ret;
//        int i = 0;
//        while (k--)
//        {
//            ret.push_back(sortVector[i].first);
//            ++i;
//        }
//        return ret;
//
//    }
//};
//
//
//int main()
//{
//    vector<string> wd;
//    wd.push_back("i");
//    wd.push_back("love");
//    wd.push_back("leetcode");
//    wd.push_back("i");
//    wd.push_back("love");
//    wd.push_back("coding");
//
//    //= "i", "love", "leetcode", "i", "love", "coding";
//    Solution s;
//    vector<string> ret = s.topKFrequent(wd, 2);
//    for (auto e : ret)
//    {
//        cout << e << " ";
//    }
//    cout << endl;
//    return 0;
//}


class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);

        for (int i = 0; i < numRows; i++)
        {
            vv[i].reserve(i + 1);
            vv[i][0] = 1;
            vv[i][i] = 1;
        }
        for (int i = 0; i < numRows; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (vv[i][j] != 1)
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
            }
        }
        return vv;
    }
};
//
//int main()
//{
//    /*Solution s;
//    vector<vector<int>> ret = s.generate(5);
//    for (int i = 0; i < 5; i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            cout << ret[i][j] << " ";
//        }
//        cout << endl;
//    }
//    cout << endl;*/
//
//    
//    return 0;
//}